package leetcode

//https://leetcode.com/problems/remove-nth-node-from-end-of-list/

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {

    var header = head
    var prev = head
    var tail = head

    //tail 和header 相距 n个节点
    var m = n
    while (m > 1) {
        tail = tail?.next
        m--
    }

    //tail 和header 同时移动

    while (tail?.next != null) {
        tail = tail.next
        prev = header
        header = header?.next
    }
    if (prev != header) { //remove head
        prev?.next = header?.next
    }else{
        //prev和header 重合,直接删除头，因为此时prev,header没有移动过
        return header?.next
    }
    return head

}

